In the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be used to find many other properties of the graph, see spectral graph theory. Cheeger's inequality from Riemannian Geometry has a discrete analogue involving the Laplacian Matrix, this is perhaps the most important theorem in Spectral Graph theory and one of the most useful facts in algorithmic applications. It approximates the sparsest cut of a graph through the second eigenvalue of its Laplacian.
Contents |
Given a simple graph G with n vertices, its Laplacian matrix is defined as:[1]
That is, it is the difference of the degree matrix and the adjacency matrix of the graph. In the case of directed graphs, either the indegree or outdegree might be used, depending on the application.
The normalized Laplacian matrix is defined as:[1]
Here is a simple example of a labeled graph and its Laplacian matrix.
Labeled graph | Laplacian matrix |
---|---|
For a graph G and its Laplacian matrix L with eigenvalues :
If we define a signed edge adjacency matrix M with element Mev for edge e (connecting vertex i and j, with i < j) and vertex v given by
then the Laplacian matrix L satisifies
where is the matrix transpose of M.
The deformed Laplacian is commonly defined as
where I is the unit matrix, A is the adjacency matrix, and D is the degree matrix, and s is a (complex-valued) number. Note that normal Laplacian is just .
The Laplacian matrix can be interpreted as a matrix representation of a particular case of the negative discrete Laplace operator. Such an interpretation allows one, e.g., to generalise the Laplacian matrix to the case of graphs with an infinite number of vertices and edges, leading to a Laplacian matrix of an infinite size.
The graph Laplacian matrix can be further viewed as a matrix form of an approximation to the negative Laplacian operator obtained by the fdm. In this interpretation, every graph vertex is treated as a grid point, the local connectivity of the vertex determines the finite difference approximation stencil at this grid point, the grid size is always one for every edge, and there are no constraints in any grid points, which corresponds the case of the homogeneous Neumann boundary condition, i.e., free boundary.